// @coding: utf8

#include <iostream>
#include <vector>
#include <random>

void dump_vector(std::vector<int>& vec)
{
    std::cout << "dump_vector: " << std::endl;
    for (auto n : vec)
    {
        std::cout << n << ",";
    }
    std::cout << std::endl;
}

// 合并两个有序array
void merge(int* data, int left, int mid, int right)
{
    int cnt = right - left + 1;
    int* tmp_data = new int[cnt];
    int left_pos = left;
    int right_pos = mid + 1;
    int tmp_pos = 0;
    while (left_pos <= mid && right_pos <= right)
    {
        if (data[left_pos] < data[right_pos])
        {
            tmp_data[tmp_pos++] = data[left_pos++];
        }
        else
        {
            tmp_data[tmp_pos++] = data[right_pos++];
        }
    }
    while (left_pos <= mid) tmp_data[tmp_pos++] = data[left_pos++];
    while (right_pos <= right) tmp_data[tmp_pos++] = data[right_pos++];
    tmp_pos = 0;
    left_pos = left;
    while (tmp_pos < cnt)
    {
        data[left_pos++] = tmp_data[tmp_pos++];
    }


    delete[] tmp_data;
}

void merge_sort(int* data, int left, int right)
{
    // 只有一个元素时 left == right
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    merge_sort(data, left, mid);
    merge_sort(data, mid + 1, right);
    merge(data, left, mid, right);
}

int main()
{
    std::vector<int> vec;
    int cnt = 6;
    for (int n = 0; n < cnt; ++n)
    {
        vec.push_back(rand() % 10);
        //vec.push_back(cnt - n);
    }

    merge_sort(vec.data(), 0, vec.size() - 1);

    dump_vector(vec);

    return 0;
}